package com.mjf.sort;

import java.util.Arrays;

/**
 * 快速排序
 * <p>
 * 思路：<br>
 * 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
 */
public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {-9, 78, 0, 23, -567, 70};
//        int[] arr = {1, 2, 3, 4, 0, 4, 5};
        int[] arr = {49, 38, 65, 97, 76, 13, 27, 49};
        System.out.println("排序前: " + Arrays.toString(arr));
        quickSort(0, arr.length - 1, arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }

    /**
     * 快速排序
     *
     * @param left  开始左坐标
     * @param right 开始右坐标
     * @param arr   待排序数组
     */
    public static void quickSort(int left, int right, int[] arr) {
        // 左坐标大于等于右坐标时，直接退出，没有需要进行排序的序列
        if (left >= right) {
            return;
        }

        // 基准坐标为左坐标
        int pivotIndex = left;
        // 基准元素
        int pivot = arr[pivotIndex];
        int r = right;
        int l = left + 1;
        int temp;

        while (l < r) {
            // 从右坐标开始找到一个比基准元素小的值后退出循环
            while (arr[r] >= pivot && l < r) {
                r--;
            }
            // 从左坐标+1开始找到一个不小于基准元素的值后退出循环
            while (arr[l] < pivot && l < r) {
                l++;
            }
            if (l < r) {
                // 交换l与r坐标的元素
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        // 如果基准元素大于l位置元素，就交换位置
        if (arr[pivotIndex] > arr[l]) {
            temp = arr[pivotIndex];
            arr[pivotIndex] = arr[l];
            arr[l] = temp;
            pivotIndex = l;
        }

        // 此时基准左边元素都比它小，右边元素都比它大
        // 递归对基准元素左右两边的数组进行快速排序
        // 对[left ... pivotIndex-1]进行快速排序
        quickSort(left, pivotIndex - 1, arr);
        // 对[pivotIndex+1 ... right]进行快速排序
        quickSort(pivotIndex + 1, right, arr);
    }
}
